﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PhraseCorrector.SpellLook
{
    /// <summary>
    /// 一个可扩展的组块数组，优化了添加操作而不支持删除大量元素，
    /// 以友好的方式存储数据，不会创建单个大数组对象，可以在不需要复制整个底层数组内容的情况下进行扩展。
    /// </summary>
    public class ChunkArray<T>
    {

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////  
        /// <summary>
        /// 每个块的大小，必须是2的幂次方以便进行优化。
        /// </summary>
        private const int ChunkSize= 4096;

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////  
        /// <summary>
        /// 右移位数，用于执行除以ChunkSize的操作，用于优化索引计算。
        /// </summary>
        private const int DivShift= 12;

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////    
        /// <summary>
        /// 块数组，每个块是一个元素数组。
        /// </summary>
        public T[][] Values { get; private set; }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////   
        /// <summary>
        /// 当前ChunkArray中的元素数量。
        /// </summary>
        public int Count { get; private set; }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 使用指定的初始容量初始化ChunkArray的新实例。
        /// </summary>
        /// <param name="initialCapacity">初始容量。</param>
        public ChunkArray(int initialCapacity)
        {
            // 计算所需的块数量
            int chunks= (initialCapacity + ChunkSize - 1) / ChunkSize;
            Values= new T[chunks][];
            for (int i= 0; i < Values.Length; i++) Values[i]= new T[ChunkSize];
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 添加一个新元素到列表中，并返回其索引。
        /// </summary>
        /// <param name="value">要添加的元素。</param>
        /// <returns>添加元素后的索引。</returns>
        public int Add(T value)
        {
            if (Count== Capacity)
            {
                var newValues= new T[Values.Length + 1][];
                // 只需复制块数组列表，而不是块内的数据
                Array.Copy(Values, newValues, Values.Length);
                newValues[Values.Length]= new T[ChunkSize];
                Values= newValues;
            }
            Values[Row(Count)][Col(Count)]= value;
            Count++;
            return Count - 1;
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 清空列表中的所有元素。
        /// </summary>
        public void Clear()
        {
            Count= 0;
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 获取或设置指定索引处的元素。
        /// </summary>
        /// <param name="index">元素的索引。</param>
        /// <returns>指定索引处的元素。</returns>
        public T this[int index]
        {
            get { return Values[Row(index)][Col(index)]; }
            set { Values[Row(index)][Col(index)]= value; }
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 计算当前ChunkArray的总容量。
        /// </summary>
        /// <returns>总容量。</returns>
        private int Capacity=> Values.Length * ChunkSize;

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 根据索引计算所在块的行号。
        /// </summary>
        /// <param name="index">元素索引。</param>
        /// <returns>行号。</returns>
        private int Row(int index)=> index >> DivShift;

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 根据索引计算在块中的列号。
        /// </summary>
        /// <param name="index">元素索引。</param>
        /// <returns>列号。</returns>
        private int Col(int index)=> index & ChunkSize - 1;
    }
}
